package com.zlk.algorithm.dataStructure.linkList03;
import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName LinkQuickSort
 * @description:给定一个单链表的头节点head，给定一个整数n，将链表按n划分成左边<n、中间==n、右边>n，且保持原来的相对次序
 * @author: slfang
 * @create: 2024-02-01 14:44
 * @Version 1.0
 **/
public class Code11_LinkQuickSort {

    @Test
    public void test(){
        SimpleNode test = null;
        test = new SimpleNode(1);
        test.next = new SimpleNode(2);
        test.next.next = new SimpleNode(0);
        test.next.next.next = new SimpleNode(6);
        test.next.next.next.next = new SimpleNode(8);
        test.next.next.next.next.next = new SimpleNode(4);
        test.next.next.next.next.next.next = new SimpleNode(5);
        test.next.next.next.next.next.next.next = new SimpleNode(1);
        test.next.next.next.next.next.next.next.next = new SimpleNode(0);
        SimpleNode simpleNode = quickSort(test, 8);

        LinkUtils.printLinkedList(simpleNode);

    }
    private SimpleNode quickSort(SimpleNode node,int k) {
        SimpleNode headNodeStart = null;
        SimpleNode headNodeEnd   = null;
        SimpleNode midNodeStart   = null;
        SimpleNode midNodeEnd   = null;
        SimpleNode tailNodeStart   = null;
        SimpleNode tailNodeEnd   = null;
        SimpleNode next   = null;

        while (node!=null){
            next = node.next;
            // todo 产生新链路之后必定要断链老链路不然会产生回路  非常重要
            node.next = null;
            if(node.value<k){
                if(headNodeStart == null){
                    headNodeStart = node;
                    headNodeEnd = node;
                }else{
                    headNodeEnd.next = node;
                    headNodeEnd = node;
                }

            }else if(node.value==k){
                if(midNodeStart == null){
                    midNodeStart = node;
                    midNodeEnd = node;
                }else{
                    midNodeEnd.next = node;
                    midNodeEnd = node;
                }

            }else{
                if(tailNodeStart == null){
                    tailNodeStart = node;
                    tailNodeEnd = node;
                }else{
                    tailNodeEnd.next = node;
                    tailNodeEnd = node;
                }
            }
            node = next;
        }
        // 小于区域的尾巴，连等于区域的头，等于区域的尾巴连大于区域的头
        //如果有小于区域
        if(headNodeEnd!=null){
            headNodeEnd.next = midNodeStart;
            //如果有等于区域就使用等于区域，没有就用小于区域尾节点
            midNodeEnd = midNodeEnd==null?headNodeStart:midNodeEnd;
        }
        // eT 尽量不为空的尾巴节点
        if (midNodeEnd != null) { // 如果小于区域和等于区域，不是都没有
            midNodeEnd.next = tailNodeStart;
        }
        return headNodeStart != null ? headNodeStart : (midNodeStart != null ? midNodeStart : tailNodeStart);
    }


}
